class Solution {
public:
    string reorganizeString(string s) {
        int hash[26] = {0};
        char mostVal = s[0];
        int maxCount = 0;
        for(auto& e : s) // 统计每个数出现的频次
        {
            ++hash[e - 'a'];
            if(maxCount < hash[e - 'a'])
            {
                maxCount = hash[e - 'a'];
                mostVal = e;
            }
        }
        
        int n = s.size(), index = 0;
        if(maxCount > (n + 1) / 2)
            return "";
        string ret(n, ' ');
        for(int i = 0; i < maxCount; ++i) // 先处理出现次数最多的数
        {
            ret[index] = mostVal;
            index += 2;
        }
 
        hash[mostVal - 'a'] = 0;
        for(int i = 0; i < 26; ++i) // 处理剩下的数
        {
            for(int j = 0; j < hash[i]; ++j)
            {
                if(index >= n)
                    index = 1;
                ret[index] = i + 'a';
                index += 2;
            }
        }
        return ret;
    }
};